package com.zklh.leetcode.other.problem62;


import java.math.BigInteger;

/**
 * 非动态规划实现, 数学排列组合实现
 * , 注意int值溢出的问题
 */
class Solution2  implements SolutionInterface{

    @Override
    public int uniquePaths(int m, int n) {
        m--;
        n--;
        BigInteger result = new BigInteger("1");
        for(int i = m+1;i<=m+n; i++){
            result = result.multiply(new BigInteger(i+""));
        }

        BigInteger tmp = new BigInteger("1");
        for(int i = n; i > 0; i--){
            tmp = tmp.multiply(new BigInteger(i+""));
        }
        System.out.println(result.toString());
        System.out.println(tmp.toString());
        return result.divide(tmp).intValue();
    }



    public static void main(String[] args){
        Solution2 solution = new Solution2();
        System.out.println(solution.uniquePaths(1, 100));
    }
    
}
